Lliwio graffiau

Lliwio graffiau

Enghraifft o'r canlynol	problem cyfrifiannu
Math	graph labeling
Ffeiliau perthnasol ar Gomin Wicimedia

Mewn theori graffiau, mae lliwio graffiau yn achos arbennig o labelu graffiau; mae'n aseiniad o labeli a elwir yn draddodiadol yn "lliwiau" i elfennau o graff yn amodol ar rai cyfyngiadau. Yn ei ffurf symlaf, mae'n ffordd o liwio fertigau graff fel nad oes unrhyw ddau fertig gyfagos o'r un lliw; gelwir hyn yn lliwio fertigau. Yn yr un modd, mae lliwio ymylon yn aseinio lliw i bob ymyl fel nad oes dwy ymyl gyfagos o'r un lliw, ac mae lliwio wynebau ar graff planar yn aseinio lliw i bob wyneb neu ranbarth fel nad oes gan unrhyw ddau wyneb sy'n rhannu ffin yr un lliw.

Lliwio fertig yw man cychwyn lliwio graffiau. Gellir trawsnewid problemau lliwio eraill i mewn i'r fersiwn fertig. Er enghraifft, lliwiad ymylon graff yw lliwiad vertigau ei graff llinell, a lliwiad wynebau graff planar yw lliwiad fertig ei ddeuol. Fodd bynnag, mae problemau lliwio nad ydynt yn lliwio fertig yn aml yn cael eu nodi a'u hastudio fel y mae. Mae hynny'n rhannol ar gyfer persbectif, ac yn rhannol oherwydd bod rhai problemau'n cael eu hastudio orau ar ffurf nad yw'n ffurf fertig, fel er enghraifft lliwio ymylon.

Mae'r confensiwn o ddefnyddio lliwiau yn tarddu o liwio gwledydd ar fap, lle mae pob wyneb wedi'i liwio'n llythrennol. Cafodd hyn ei gyffredinoli i liwio wynebau graff fewnblannedig yn yr plân. Erbyn deuoliaeth planar mae'n cywerth â lliwio'r fertigau, ac ar y ffurf hon mae'n cyffredinoli i bob graff. Mewn cynrychioliadau mathemategol a chyfrifiadurol, mae'n arferol i ddefnyddio'r gyfanrifau positif cyntaf fel y "lliwiau". Yn gyffredinol, gallwn ddefnyddio unrhyw set meidraidd fel y "set lliwiau". Mae natur y broblem lliwio yn dibynnu ar nifer y lliwiau ond nid ar beth ydyn nhw.

Mae lliwio graffiau yn mwynhau nifer o gymwysiadau ymarferol yn ogystal â heriau damcaniaethol. Heblaw am y mathau clasurol o broblemau, gellir gosod gwahanol gyfyngiadau ar y graff, neu ar y ffordd y mae lliw yn cael ei neilltuo, neu hyd yn oed ar y lliw ei hun. Mae hyd yn oed wedi cyrraedd poblogrwydd gyda'r cyhoedd ar ffurf y pos rhif poblogaidd Sudoku. Mae lliwio graffiau yn dal i fod yn faes ymchwil gweithredol iawn.